import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: lishuo
 * Date: 2023-01-11
 * Time: 17:15
 */
public class Myheap {
    public int[] elem;
    public int usedSize;

//    public Myheap() {
//        this.elem = new int[10];
//    }

    public void Init(int[] array) {
        this.elem = Arrays.copyOf(array, array.length);
        this.usedSize = array.length;

    }

    public void creatHeap(int[] array) {
        Init(array);

        for (int parent = (usedSize-1-1)/2; parent >= 0 ; parent--) {
            SshiftDown(parent,usedSize);
        }
    }

    //向下调整[创建大根堆]
    private void BshiftDown(int parent, int len) {
        //有左孩子
        int child = 2 * parent + 1;//这里是+1！！！

        while (child < len) {
            //有右孩子
            if (child + 1 < len && elem[child] < elem[child + 1]) {
                child++;
            }
            //此时childe一定是左右孩子的最大值的下标
            if (elem[child] > elem[parent]) {
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;

                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }

    //创建小根堆
    private void SshiftDown(int parent, int len) {
        //有左孩子
        int child = 2 * parent + 1;//这里是+1！！！

        while (child < len) {
            //有右孩子
            if (child + 1 < len && elem[child] > elem[child + 1]) {
                child++;
            }
            //此时childe一定是左右孩子的最大值的下标
            if (elem[child] < elem[parent]) {
                int tmp = elem[parent];
                elem[parent] = elem[child];
                elem[child] = tmp;

                parent = child;
                child = 2 * parent + 1;
            } else {
                break;
            }
        }
    }
}
